package Exams.FeiBu;

import CommonClass.ListNode;


public class q2 {
    /*
    会员题369
    链表加一
    但是是从后向前的计数方式，因此相当于反转链表后 利用两数相加的方式计算后
    再次反转链表
     */
    public ListNode plusOne(ListNode head) {
        ListNode node = reverse(head);
        ListNode cur = node;
        ListNode pre = null;
        int cnt = 1;

        // 依次按位加
        while (cur != null) {
            int temp = cur.val + cnt;
            cur.val = temp % 10;
            cnt = temp / 10;

            pre = cur;
            cur = cur.next;
        }

        // 若最高位有进位则再插入一个节点
        if (cnt != 0) pre.next = new ListNode(cnt);

        return reverse(node);
    }

    private ListNode reverse(ListNode head) {
        ListNode pre = null;
        ListNode cur = head;

        while (cur != null) {
            ListNode next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }

        return pre;
    }
}
